package Aula10;

public class QuickMedia {
	
	public void swap(int[] array, int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

	
	public int menorDiferenca(int[] vetor, double media){
		double menorDif = Math.abs(media - vetor[0]);
		int index = 0;
		for(int i = 1; i < vetor.length; i++){
			if (menorDif > Math.abs(media - vetor[i])){
				menorDif = Math.abs(media - vetor[i]);
				index = i;
			}
		}
		return index;
	}
	
	
	public int partition(int[] array, int begin, int end) {
		double media = 0;
		for(int i = begin; i < end; i++){
			media += array[i];
		}
		media = media/array.length;
		int index = menorDiferenca(array, media);
		int pivot = array[index];
		swap(array, index, end);
		for (int i = index = begin; i < end; ++i) {
			if (array[i]<= (pivot)) {
				swap(array, index++, i);
			}
		}
		swap(array, index, end);
		return (index);
	}

	public void qsort(int[] array, int begin, int end) {
		if (end > begin) {
			int index = partition(array, begin, end);
			qsort(array, begin, index - 1);
			qsort(array, index + 1, end);
		}
	}

	public void sort(int[] array) {
		qsort(array, 0, array.length - 1);
	}
}
